home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2001 May / may_2001.iso / intercd / root / Multimedia / ^DivX_Article / virtualdub / VirtualDub-source-1_4d / FrameSubset.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-03-20  |  8.4 KB  |  408 lines
  1. //    VirtualDub - Video processing and capture application
  2. //    Copyright (C) 1998-2001 Avery Lee
  3. //
  4. //    This program is free software; you can redistribute it and/or modify
  5. //    it under the terms of the GNU General Public License as published by
  6. //    the Free Software Foundation; either version 2 of the License, or
  7. //    (at your option) any later version.
  8. //
  9. //    This program is distributed in the hope that it will be useful,
  10. //    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12. //    GNU General Public License for more details.
  13. //
  14. //    You should have received a copy of the GNU General Public License
  15. //    along with this program; if not, write to the Free Software
  16. //    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  
  18. #include <crtdbg.h>
  19.  
  20. #include "FrameSubset.h"
  21. #include "Error.h"
  22.  
  23. FrameSubset::FrameSubset() {
  24. }
  25.  
  26. FrameSubset::FrameSubset(int length) {
  27.     addRange(0, length);
  28. }
  29.  
  30. void FrameSubset::clear() {
  31.     FrameSubsetNode *pfsn;
  32.  
  33.     while(pfsn = list.RemoveHead())
  34.         delete pfsn;
  35. }
  36.  
  37. void FrameSubset::addFrom(FrameSubset& src) {
  38.     FrameSubsetNode *pfsn_next, *pfsn = src.list.AtHead();
  39.  
  40.     while(pfsn_next = pfsn->NextFromHead()) {
  41.         addRangeMerge(pfsn->start, pfsn->len);
  42.         pfsn = pfsn_next;
  43.     }
  44. }
  45.  
  46. void FrameSubset::addRange(int start, int len) {
  47.     FrameSubsetNode *pfsn = new FrameSubsetNode(start, len);
  48.  
  49.     if (!pfsn)
  50.         throw MyMemoryError();
  51.  
  52.     pfsn->start        = start;
  53.     pfsn->len        = len;
  54.  
  55.     list.AddTail(pfsn);
  56. }
  57.  
  58. void FrameSubset::addRangeMerge(int start, int len) {
  59.     FrameSubsetNode *pfsn_next, *pfsn = list.AtHead();
  60.  
  61.     while(pfsn_next = pfsn->NextFromHead()) {
  62.         if (start + len < pfsn->start) {                // Isolated -- insert
  63.             FrameSubsetNode *pfsn_new = new FrameSubsetNode(start, len);
  64.  
  65.             if (!pfsn_new)
  66.                 throw MyMemoryError();
  67.  
  68.             pfsn_new->InsertBefore(pfsn);
  69.             return;
  70.         } else if (start + len >= pfsn->start && start <= pfsn->start+pfsn->len) {        // Overlap!
  71.             if (start+len > pfsn->start+pfsn->len) {    // < A [ B ] > or [ B <] A > cases
  72.                 if (pfsn->start < start) {
  73.                     len += (start - pfsn->start);
  74.                     start = pfsn->start;
  75.                 }
  76.  
  77.                 pfsn->Remove();
  78.                 delete pfsn;
  79.             } else {                                    // < A [> B ], <A | B>, or [ <A> B ] cases
  80.                 if (pfsn->start > start) {
  81.                     len += (start - pfsn->start);
  82.                     pfsn->start = start;
  83.                 }
  84. #ifdef _DEBUG
  85.                 goto check_list;
  86. #else
  87.                 return;
  88. #endif
  89.             }
  90.         }
  91.  
  92.         pfsn = pfsn_next;
  93.     }
  94.  
  95.     // List is empty or element falls after last element
  96.  
  97.     addRange(start, len);
  98.  
  99. #ifdef _DEBUG
  100. check_list:
  101.     int lastpt = -1;
  102.  
  103.     pfsn = list.AtHead();
  104.     while(pfsn_next = pfsn->NextFromHead()) {
  105.         if (pfsn->start <= lastpt) {
  106.             throw MyError("addRangeMerge: FAILED!!  %d <= %d\n", pfsn->start, lastpt);
  107.         }
  108.  
  109.         lastpt = pfsn->start + pfsn->len;
  110.  
  111.         pfsn = pfsn_next;
  112.     }
  113.  
  114. #endif
  115. }
  116.  
  117. FrameSubset::~FrameSubset() {
  118.     clear();
  119. }
  120.  
  121. int FrameSubset::getTotalFrames() {
  122.     FrameSubsetNode *pfsn_next, *pfsn = list.AtHead();
  123.     int iFrames = 0;
  124.  
  125.     while(pfsn_next = pfsn->NextFromHead()) {
  126.         iFrames += pfsn->len;
  127.  
  128.         pfsn = pfsn_next;
  129.     }
  130.  
  131.     return iFrames;
  132. }
  133.  
  134. int FrameSubset::lookupFrame(int frame) {
  135.     int len = 1;
  136.  
  137.     return lookupRange(frame, len);
  138. }
  139.  
  140. int FrameSubset::revLookupFrame(int frame) {
  141.     FrameSubsetNode *pfsn_next, *pfsn = list.AtHead();
  142.     int iSrcFrame = 0;
  143.  
  144.     while(pfsn_next = pfsn->NextFromHead()) {
  145.         if (frame >= pfsn->start && frame < pfsn->start+pfsn->len)
  146.             return iSrcFrame + (frame - pfsn->start);
  147.  
  148.         iSrcFrame += pfsn->len;
  149.  
  150.         pfsn = pfsn_next;
  151.     }
  152.  
  153.     return -1;
  154. }
  155.  
  156. int FrameSubset::lookupRange(int start, int& len) {
  157.     int offset;
  158.     FrameSubsetNode *pfsn = findNode(offset, start);
  159.  
  160.     if (!pfsn) return -1;
  161.  
  162.     len = pfsn->len - offset;
  163.     return pfsn->start + offset;
  164. }
  165.  
  166. void FrameSubset::deleteRange(int start, int len) {
  167.     int offset;
  168.     FrameSubsetNode *pfsn = findNode(offset, start), *pfsn_t;
  169.  
  170.     if (!pfsn)
  171.         return;
  172.  
  173.     while((pfsn_t = pfsn->NextFromHead()) && len>0) {
  174.         if (pfsn->len - offset > len) {
  175.             if (offset) {
  176.                 FrameSubsetNode *pfsn2 = new FrameSubsetNode;
  177.  
  178.                 if (!pfsn2) throw MyMemoryError();
  179.  
  180.                 pfsn2->start    = pfsn->start + offset + len;
  181.                 pfsn2->len        = pfsn->len - (offset + len);
  182.                 pfsn->len        = offset;
  183.                 pfsn2->InsertAfter(pfsn);
  184.             } else {
  185.                 pfsn->start += len;
  186.                 pfsn->len -= len;
  187.             }
  188.  
  189.             break;
  190.         } else {
  191.             if (offset) {
  192.                 len -= pfsn->len - offset;
  193.                 pfsn->len = offset;
  194.             } else {
  195.                 len -= pfsn->len;
  196.                 deleteNode(pfsn);
  197.             }
  198.         }
  199.  
  200.         offset = 0;
  201.         pfsn = pfsn_t;
  202.     }
  203.  
  204. #ifdef _DEBUG
  205.     {
  206.         FrameSubsetNode *pfsn;
  207.  
  208.         _RPT0(0,"Subset dump:\n");
  209.  
  210.         if (pfsn = getFirstFrame())
  211.             do {
  212.                 _RPT2(0,"\tNode: start %ld, len %ld\n", pfsn->start, pfsn->len);
  213.             } while(pfsn = getNextFrame(pfsn));
  214.  
  215.     }
  216. #endif
  217. }
  218.  
  219. void FrameSubset::clipToRange(int start, int len) {
  220.     FrameSubsetNode *pfsn = list.AtHead(), *pfsn_t;
  221.  
  222.     if (!pfsn)
  223.         return;
  224.  
  225.     while(pfsn_t = pfsn->NextFromHead()) {
  226.         if (pfsn->start >= start) {
  227.             if (pfsn->start > start+len)
  228.                 deleteNode(pfsn);
  229.             else {
  230.                 if (pfsn->start+pfsn->len > start+len)
  231.                     pfsn->len = start+len - pfsn->start;
  232.  
  233.                 if (pfsn->start < start) {
  234.                     pfsn->len += pfsn->start - start;
  235.                     pfsn->start = start;
  236.                 }
  237.             }
  238.         } else if (pfsn->start + pfsn->len >= start) {
  239.             pfsn->len += pfsn->start - start;
  240.             pfsn->start = start;
  241.         } else
  242.             deleteNode(pfsn);
  243.  
  244.         pfsn = pfsn_t;
  245.     }
  246. }
  247.  
  248. void FrameSubset::clip(int start, int len) {
  249.     deleteRange(0, start);
  250.     deleteRange(len, 0x7FFFFFFF);
  251. }
  252.  
  253. void FrameSubset::offset(int off) {
  254.     FrameSubsetNode *pfsn = list.AtHead(), *pfsn_t;
  255.  
  256.     if (!pfsn)
  257.         return;
  258.  
  259.     while(pfsn_t = pfsn->NextFromHead()) {
  260.         pfsn->start += off;
  261.  
  262.         pfsn = pfsn_t;
  263.     }
  264. }
  265.  
  266. void FrameSubset::deleteNode(FrameSubsetNode *pfsn) {
  267.     pfsn->Remove();
  268.     delete pfsn;
  269.  
  270. }
  271.  
  272. FrameSubsetNode *FrameSubset::findNode(int& poffset, int iDstFrame) {
  273.     FrameSubsetNode *pfsn_next, *pfsn = list.AtHead();
  274.  
  275.     if (iDstFrame<0)
  276.         return NULL;
  277.  
  278.     while((pfsn_next = pfsn->NextFromHead()) && iDstFrame>=0) {
  279.         if (iDstFrame < pfsn->len) {
  280.             poffset = iDstFrame;
  281.             return pfsn;
  282.         }
  283.  
  284.         iDstFrame -= pfsn->len;
  285.  
  286.         pfsn = pfsn_next;
  287.     }
  288.  
  289.     return NULL;
  290. }
  291.  
  292. ///////////////////////////////////////////////////////////////////////////
  293.  
  294. #ifdef _DEBUG
  295. class FrameSubsetClassVerifier {
  296. public:
  297.     void check(FrameSubset& fs, int test, ...) {
  298.         va_list val;
  299.         FrameSubsetNode *pfsn = fs.getFirstFrame();
  300.  
  301.         va_start(val, test);
  302.         while(pfsn) {
  303.             if (pfsn->start != va_arg(val, int))
  304.                 throw MyError("fail test #%dA", test);
  305.             if (pfsn->len != va_arg(val, int))
  306.                 throw MyError("fail test #%dB", test);
  307.  
  308.             pfsn = fs.getNextFrame(pfsn);
  309.         }
  310.         if (va_arg(val, int) != -1)
  311.             throw MyError("fail test #%dC", test);
  312.  
  313.         va_end(val);
  314.  
  315.     }
  316.  
  317.     FrameSubsetClassVerifier() {
  318.         _RPT0(0,"Verifying class: FrameSubset\n");
  319.         try {
  320.             {
  321.                 FrameSubset fs;
  322.  
  323.                 fs.addRangeMerge(10, 10);
  324.                 fs.addRangeMerge(30, 10);
  325.                 fs.addRangeMerge(50, 10);
  326.                 check(fs, 1, 10, 10, 30, 10, 50, 10, -1);
  327.             }
  328.  
  329.             {
  330.                 FrameSubset fs;
  331.  
  332.                 fs.addRangeMerge(10, 10);
  333.                 fs.addRangeMerge(20, 10);
  334.                 fs.addRangeMerge(30, 10);
  335.                 check(fs, 2, 10, 30, -1);
  336.             }
  337.  
  338.             {
  339.                 FrameSubset fs;
  340.  
  341.                 fs.addRangeMerge(10, 10);
  342.                 fs.addRangeMerge(20, 10);
  343.                 fs.addRangeMerge(50, 10);
  344.                 check(fs, 3, 10, 20, 50, 10, -1);
  345.             }
  346.  
  347.             {
  348.                 FrameSubset fs;
  349.  
  350.                 fs.addRangeMerge(10, 10);
  351.                 fs.addRangeMerge(40, 10);
  352.                 fs.addRangeMerge(50, 10);
  353.                 check(fs, 4, 10, 10, 40, 20, -1);
  354.             }
  355.  
  356.             {
  357.                 FrameSubset fs;
  358.  
  359.                 fs.addRangeMerge(10, 10);
  360.                 fs.addRangeMerge(15, 10);
  361.                 fs.addRangeMerge(50, 10);
  362.                 check(fs, 5, 10, 15, 50, 10, -1);
  363.             }
  364.  
  365.             {
  366.                 FrameSubset fs;
  367.  
  368.                 fs.addRangeMerge(10, 10);
  369.                 fs.addRangeMerge(45, 10);
  370.                 fs.addRangeMerge(50, 10);
  371.                 check(fs, 6, 10, 10, 45, 15, -1);
  372.             }
  373.  
  374.             {
  375.                 FrameSubset fs;
  376.  
  377.                 fs.addRangeMerge(10, 10);
  378.                 fs.addRangeMerge(15, 30);
  379.                 fs.addRangeMerge(50, 10);
  380.                 check(fs, 7, 10, 35, 50, 10, -1);
  381.             }
  382.  
  383.             {
  384.                 FrameSubset fs;
  385.  
  386.                 fs.addRangeMerge(10, 10);
  387.                 fs.addRangeMerge(8, 48);
  388.                 fs.addRangeMerge(50, 10);
  389.                 check(fs, 8, 8, 52, -1);
  390.             }
  391.  
  392.             {
  393.                 FrameSubset fs;
  394.  
  395.                 fs.addRangeMerge(10, 10);
  396.                 fs.addRangeMerge(8, 100);
  397.                 fs.addRangeMerge(50, 10);
  398.                 check(fs, 9, 8, 100, -1);
  399.             }
  400.  
  401.  
  402.         } catch(MyError e) {
  403.             e.post(NULL, "Class verify failed: FrameSubset");
  404.         }
  405.     }
  406. } g_ClassVerifyFrameSubset;
  407. #endif
  408.